package nju.cs.ics.hooting.dp;
/**
 * 
 * @author Hooting<Hootingnju@gmail.com>
 *
 * Date:2013-9-8上午9:29:50
 * Given a sequence of N numbers - A[1] , A[2] , ..., A[N] .
 * Find the length of the longest non-decreasing sequence. 
 */
public class LongestSequence {
	public static void main(String[] args) {
		int[] array = {5, 3, 4, 8, 6, 7};
		getLength(array, 6);
	}
	
	public static void getLength(int[] array, int num){
		int[] length = new int[num];
		for(int i = 0; i < num; i++){
			length[i] = 1;
		}
		for(int i = 0; i < num; i++){
			for(int j = 0; j < i; j++){
				if (array[i] >= array[j] && length[i] < 1 + length[j]){
					length[i] = 1 + length[j];
				}
			}
		}
		for(int i = 0; i < num; i++){
			System.out.printf("i=[%d],length=[%d]\n", i, length[i]);
		}
	}

}
